1969(EDU div2)

A. Two Friends

莫诺卡普想开一个派对。他有 $n$ 个朋友，他希望至少有 $2$ 个朋友参加他的派对。

$i$ 这个朋友最好的朋友是 $p_{i}$ 。所有的 $p_{i}$ 都是不同的，而每一个 $i \in [1, n]$ 都是 $p_{i} \neq i$ 。

Monocarp 可以向朋友发送邀请。如果第 $i$ 个朋友和第 $p_{i}$ 个朋友都收到了邀请，那么第 $i$ 个朋友就会来参加聚会（注意，第 $p_{i}$ 个朋友不必真的来参加聚会）。每份邀请函都恰好发给其中一位朋友。

例如，如果 $p = [3, 1, 2, 5, 4]$ 和 Monocarp 向好友 $[1, 2, 4, 5]$ 发送了邀请，那么好友 $[2, 4, 5]$ 就会来参加聚会。朋友 $1$ 不会来，因为他最好的朋友没有收到邀请；朋友 $3$ 不会来，因为他没有收到邀请。

计算 Monocarp 至少要发出多少份邀请函，才能让至少 $2$ 个朋友来参加聚会？

可以知道答案要么是 $2$ ，要么是 $3$ ，要是存在 $(i, a_{i})$ 相反的答案就是 2 否则是 3

void solve() {
    int n;cin >> n;vector<int> a(n + 1);map<int, int>mp;
    for (int i = 1;i <= n;i++)cin >> a[i], mp[a[i]] = i;
    int ok = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            if (a[i] == j && i == a[j])ok = 1;
        }
    }
    if (ok)cout << 2 << "\n";
    else cout << 3 << '\n';
}

B. Shifts and Sorting

让我们把某个字符串 $s$ 的循环移动定义为从 $s_{1} s_{2} \dots s_{n - 1} s_{n}$ 到 $s_{n} s_{1} s_{2} \dots s_{n - 1}$ 的变换。换句话说，就是将最后一个字符 $s_{n}$ 放在第一个字符之前，同时将所有其他字符向右移动。

您将得到一个二进制字符串 $s$ （一个仅由 0/1组成的字符串）。

在一次操作中，您可以选择任意子串并循环移动它。这种操作的代价等于 $r - l + 1$ （或所选子串的长度）。

您可以执行任意次数的给定操作。要使 $s$ 按非降序排序，总成本最小是多少？

#define int long long
void solve() {
    string s;cin >> s;
    int num1 = 0, ans = 0, ok = 0;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '1') {
            num1++;ok = 1;
        } else {
            if (ok) ans += num1 + 1;
        }
    }
    cout << ans << '\n';
}

C. Minimizing the Sum

给你一个长度为 $n$ 的整数数组 $a$ 。

可以执行以下操作：选择数组中的一个元素，并用其邻近元素的值替换它。

能执行上述操作最多 $k$ 次，计算数组的最小总和。

Solution

贪心无法保证正确性，如：

4 2
4 2 1 2

可以知道 $0 \leq k \leq 10$ ,也侧面说明贪心不可行。

每次某数字进行操作只会影响身边的数字，这样操作最终影响的一定是一个连续的区间，且为了最优，在对区间进行操作时不会出现重叠的现象，因此最优的答案一定是对若干个不重叠的连续的区间进行修改，

对于每个这样的区间，有以下性质：

每个区间的操作次数就是区间长度减 1
这个区间中的所有元素都是 操作之前这个区间的最小值

#define int long long
void solve() {
    int n, k;cin >> n >> k;vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    vector<vector<int>> f(n + 1, vector<int>(k + 1, 1e18));
    f[0][0] = 0;
    for (int i = 1;i <= n;i++) {
        int mi = a[i];
        for (int j = 0;i + j <= n && j <= k;j++) {
            mi = min(mi, a[i + j]);
            for (int p = 0;p + j <= k;p++) {
                f[i + j][p + j] = min(f[i + j][p + j], f[i - 1][p] + mi * (j + 1));
            }
        }
    }
    cout << *(min_element(f[n].begin(), f[n].end())) << '\n';
}

将小白月赛 92, CF (EDU 165) 补了，然后开始"DP，(图论 (LCA)，数论 (常用))"，然后开始板刷 CF~
(PS: 要考试的时候就优先突击考试)

官方题解：

void solve() {
	int n, k;cin >> n >> k;
	vector<ll> a(n);for (auto& x : a) cin >> x;
	vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 1e18));
	dp[0][0] = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j <= k; ++j) {
			ll mn = 1e18;
//从dp[i,j]->dp[i+d+1,j+d]在这之前已经进行了i个数字，j个操作，在该处操作了d次，区间长度为d+1，区间内全为mi
			for (int d = 0; j + d <= k && i + d < n; ++d) {//d代表在此区间内的操作次数
				mn = min(mn, a[i + d]);//这段区间内的最小值
				dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
			}
		}
	}
	cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';//dp[n][min(k, n - 1)]
}

D. Shop Game

爱丽丝和鲍勃正在商店里玩游戏。商店里有 $n$ 件商品；每件商品有两个参数： $a_{i}$ （爱丽丝的物品价格）和 $b_{i}$ （鲍勃的物品价格）。(鲍勃的物品价格）。

爱丽丝希望选择一个商品子集（可能是空）并购买它们。之后，Bob 会执行以下操作：

如果爱丽丝购买的物品少于 $k$ ，鲍勃可以免费拿走所有物品；
否则，他会免费拿走爱丽丝购买的 $k$ 件（由鲍勃选择是哪一个 $k$ 件），至于剩下的选择件，鲍勃会从爱丽丝那里购买，并为 $i$ /-th 件支付 $b_{i}$ 。

爱丽丝的利润等于 $\sum_{i \in S} b_{i} - \sum_{j \in T} a_{j}$ ，其中 $S$ 是鲍勃从爱丽丝处购买的物品集， $T$ 是爱丽丝从商店购买的物品集。换句话说，爱丽丝的利润就是鲍勃支付给她的金额和她购买商品所花费的金额之间的差额。

爱丽丝希望自己的利润最大化，而鲍勃希望爱丽丝的利润最小化。您的任务是计算在爱丽丝和鲍勃都采取最优行动的情况下爱丽丝的利润。

Solution

堆/前缀和/思维

在这个题目中只有可能选择 $a_{i} < b_{i}$ 的情况，不然选择了一定是亏损的，先按照 $b_{i}$ 进行排序，按照从大到小的顺序进行处理.

若 $k = 0$ 的话，就是 $\sum max (b_{i} - a_{i}, 0)$ ，否则的话就依次枚举后面的去免费拿走，若拿走的个数大于 $k$ 了，则将之前拿走的最大的那个商品去掉，继续比较，取最大值。

Jiangly 代码：

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(),
        [&](int i, int j) {
            return b[i] < b[j];
        });

    ll ans = 0;
    vector<ll> profit(n + 1);
    for (int i = 0; i < n; i++) {
        profit[i + 1] = profit[i] + max(b[p[i]] - a[p[i]], 0);
    }
    ll sum = 0;
    priority_queue<int> pq;
    for (int i = n; i >= 0; i--) {
        if (i < n) {
            pq.push(a[p[i]]);
            sum += a[p[i]];
        }
        while (pq.size() > k) {
            sum -= pq.top();
            pq.pop();
        }
        if (pq.size() == k) {
            ans = max(ans, profit[i] - sum);
        }
    }
    cout << ans << "\n";
}